package _搜索;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class _02DFS回溯 {
	// 题目：输入一个n，输出1到n的全排列
	static List<List<Integer>> list = new ArrayList<>();
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int v[] = new int[n+1];
		List<Integer> res = new ArrayList<>();
		
		dfs(n,v,res);
		
		System.out.println(list);
		
		scan.close();
		
	}
	
	public static void dfs(int n,int[] v,List<Integer> res) {
		if(res.size() == n) {
			// 这里必须是new，直接用res是引用地址的方式，后面会把res内的元素移除，会导致list中的res元素也被移除
			list.add(new ArrayList<>(res));
			return;
		}
		// 从数字1开始
		for(int i = 1;i <= n;i++) {
			// v == 1说明已经经过该路径，则跳过
			if(v[i] == 1) {
				continue;
			}
			// 没经过则加入res集合中，并且设置为1表示经过
			res.add(i);
			v[i] = 1;
			dfs(n,v,res);
			// 此时dfs进行了return，说明 res.size() == n ，达到排列最大值，则移除元素进行回退
			res.remove(res.size()-1);
			v[i] = 0;
			
		}
		
		
	}
}
